/* expect : 8 pts */
#include <bits/stdc++.h>
using namespace std;

const int N = 2010, mod = 998244353;
long long fac[N], inv[N];
inline long long C(int n, int m)
{return fac[n] * inv[m] % mod * inv[n - m] % mod;}
inline long long qpow(long long a, long long b)
{
	long long ans = 1;
	while(b)
	{
		if(b & 1) ans = ans * a % mod;
		b >>= 1, a = a * a % mod;
	}
	return ans;
}
inline void init_math()
{
	fac[0] = inv[0] = 1;
	for(int i = 1; i <= 2000; ++i) fac[i] = fac[i - 1] * i % mod;
	inv[2000] = qpow(fac[2000], mod - 2);
	for(int i = 1999; i >= 1; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
}
int T, c, n, m;
vector < int > X, Y;
namespace Subtask_1
{
	int mp[6][6]; long long comp = 1e18, res;
	struct edge {int x, y;} e[32]; int en;
	inline void solve()
	{
		en = 0; comp = 1e18, res = 0;
		for(int i = 1; i <= n; ++i)
			for(int j = i + 1; j <= n; ++j)
				e[++en] = {i, j};
		for(int mask = 0; mask < (1 << en); ++mask)
		{
			if(__builtin_popcount(mask) != m - 1) continue;
			memset(mp, 0x3f, sizeof(mp));
			for(int i = 1; i <= en; ++i)
				if((1 << (i - 1)) & mask)
					mp[e[i].x][e[i].y] = mp[e[i].y][e[i].x] = 1;
			for(int k = 1; k <= n; ++k)
				for(int i = 1; i <= n; ++i)
					for(int j = 1; j <= n; ++j)
						mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
			long long cur = 0;
			for(int i = 1; i <= m; ++i)
				cur += mp[X[i]][Y[i]];
			if(cur < comp) comp = cur, res = 0;
			if(cur == comp) ++res;
		}
		cout << -comp << " " << res << '\n';
	}
}
namespace Subtask_2
{
	long long f[N], res;
	inline long long get(int x)
	{
		if(x % 2 == 0) return 1;
		return mod - 1;
	}
	inline void solve()
	{
		cout << -(n - 1) * 2 << " ";
		f[1] = n - 1;
		for(int i = 2; i <= n; ++i)
		{
			f[i] = f[i - 1] * (n - 1) % mod;
			for(int j = 1; j < i; ++j)
				f[i] = (f[i] + f[j] * (mod - 1) % mod * get(i - j) % mod) % mod;
		}
		cout << f[n] << '\n';
	}
}
inline void sol()
{
	X.clear(), X.push_back(0);
	Y.clear(), Y.push_back(0);
	cin >> n >> m;
	for(int i = 1; i <= m; ++i)
	{
		int x, y; cin >> x >> y;
		X.push_back(x);
		Y.push_back(y);
	}
	if(1 <= c && c <= 2)
		Subtask_1::solve();
	if(3 <= c && c <= 4)
		Subtask_2::solve();
}

int main()
{
	freopen("oi.in", "r", stdin);
	freopen("oi.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	init_math();
	cin >> c >> T;
	while(T--) sol();
	return 0;
}
